package com.test.daily.leetcode.y2022.m06.day0609.v04;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/6/9 下午 09:55
 * @version: 1.0
 */
public class Solution {

    public static int longestParSubString(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        return process(str, 0, str.length);

    }

    public static int process(char[] str, int L, int R) {
        if (L == R) {
            return 1;
        }
        if (L == R - 1) { // 两个紧挨在一起
            return str[L] == str[R] ? 2 : 1;
        }
        int p1 = process(str, L, R - 1);
        int p2 = process(str, L + 1, R);
        int p3 = process(str, L + 1, R - 1);
        int p4 = str[L] == str[R] ? 2 + process(str, L + 1, R - 1) : 0;
        return Math.max(Math.max(p1, p2), Math.max(p3, p4));
    }

    public static int longestParSubString2(String s) {
        if (s == null || s.length() == 0) {
            return 0;
        }
        char[] str = s.toCharArray();
        int N = str.length;
        int[][] dp = new int[N][N];
        dp[0][0] = 1;
        for (int i = 1; i < N; i++) {
            dp[i][i] = 1;
            dp[i - 1][i] = str[i - 1] == str[i] ? 2 : 1;
        }

        for (int L = N - 3; L >= 0; L--) {
            for(int R = L + 2; R < N ; R++){
                int p1 = dp[L][R - 1];
                int p2 = dp[L + 1][R];
                int p3 = dp[L + 1][R-1];
                int p4 = str[L] == str[R] ? 2 + dp[L+1][R-1] : 0;
                dp[L][R] = Math.max(Math.max(p1, p2), Math.max(p3, p4));
            }
        }
        return dp[0][N-1];
    }
}
